#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;
typedef pair<int, int> pii;
#define mp make_pair

const int MAXN = 1000, INF = 10001000;
bool done[MAXN];
int d[MAXN];
int n, m;
int first[MAXN];
int next[MAXN];
int u[MAXN], v[MAXN], w[MAXN];

void read_graph() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) first[i] = -1;
    for (int e = 0; e < m; ++e) {
        cin >> u[e] >> v[e] >> w[e];
        next[e] = first[u[e]];
        first[u[e]] = e;
    }
}

void Dijkstra() {
    for (int i = 0; i < n; ++i) d[i] = (i == 0 ? 0 : INF);
    priority_queue<pii, vector<pii>, greater<pii> > q;
    q.push(mp(d[0], 0));
    while (!q.empty()) {
        pii u = q.top(); q.pop();
        int x = u.second;
        if (done[x]) continue;
        done[x] = true;
        for (int e = first[x]; e != -1; e = next[e]) if (d[v[e]] > d[x] + w[e]) {
            d[v[e]] = d[x] + w[e];
            q.push(mp(d[v[e]], v[e]));
        }
    }
}

int main() {
    freopen("dijkstra.in", "r", stdin);
    read_graph();
    Dijkstra();
    for (int i = 0; i < n; ++i) cout << d[i] << ' ';
    cout << endl;
}
